9643. Catalan numbers

Catalan numbers c_n are defined by the recurrence relation:

с₀ = 1,

с_n = , n > 0

Compute the n-th Catalan number modulo m.

Input. Two integers n (0 ≤ n ≤ 10⁴) and m (0 < m ≤ 10⁹).

Output. Print the value of c_n mod m.

Sample input	Sample output
5 100	42

SOLUTION

Catalan numbers

Algorithm analysis

Let’s rewrite the recurrence relation as follows:

с₀ = 1,

с_n = c₀c_n-1 + c₁c_n-2 + c₂c_n-3 + ... + c_n-1c₀, if n > 0

For example,

· с₀ = 1

· с₁ = c₀c₀ = 1,

· с₂ = c₀c₁ + c₁c₀ = 1 + 1 = 2,

· с₃ = c₀c₂ + c₁c₁ + c₂c₀ = 2 + 1 + 2 = 5,

· с₄ = c₀c₃ + c₁c₂ + c₂c₁ + c₃c₀ = 5 + 2 + 2 + 5 = 14,

· с₅ = c₀c₄ + c₁c₃ + c₂c₂ + c₃c₁ + c₄c₀ = 14 + 5 + 4 + 5 + 14 = 42

Since the value of с_n is computed based on all previous values c₀, c₁, c₂, ..., c_n-1, we will store the Catalan numbers in a linear array.

Algorithm implementation

Declare an array cat, where we’ll store the Catalan numbers: cat[i] = c_i.

long long cat[10001];

Read the input data.

scanf("%lld %lld", &n, &m);

Compute the Catalan numbers using the recurrence relation.

cat[0] = 1;

for (i = 1; i <= n; i++)

{

for (j = 0; j < i; j++)

cat[i] = (cat[i] + cat[j] * cat[i - j - 1]) % m;

}

Print the n-th Catalan number.

printf("%lld\n", cat[n]);

Python implementation

Read the input data.

n, m = map(int, input().split())

Store the values of the Catalan numbers in the list cat, where cat[i] = c_i.

cat = [0] * (n + 1)

Compute the Catalan numbers using the recurrence relation.

cat[0] = 1

for i in range(1, n + 1):

for j in range(i):

cat[i] = (cat[i] + cat[j] * cat[i - j - 1]) % m

Print the n-th Catalan number.

print(cat[n])